﻿namespace LeetCodeProject._0001_1000._001_100._61_70._064;

public class Solution
{
    public int MinPathSum(int[][] grid)
    {
        var rows = grid.Length;
        var cols = grid[0].Length;
        var result = new int[cols];
        result[0] = grid[0][0];
        for (int col = 1; col < cols; col++)
        {
            //求第一行的每个格子的数据
            result[col] = result[col - 1] + grid[0][col];
        }

        for (int row = 1; row < rows; row++)
        {
            var line = grid[row];
            result[0] += line[0];
            for (int col = 1; col < cols; col++)
            {
                result[col] = line[col] + Math.Min(result[col], result[col - 1]);
            }
        }

        return result[cols - 1];
    }
}